A compiled program is typically linked to all programs called by that program at compile time. That is, the locations of all programs called by the compiled program are resolved by a compiler, or by a linker program, and stored in a data structure within the compiled program. In most systems, this linking process is performed at compile time, which means it is performed prior to execution of a program.
The Java virtual machine (which is distributed and licensed by Sun Microsystems, Inc.), as well as some other interpreted language systems, dynamically link programs while they are running. In such systems, if during execution of a first program the first program executes a procedure call to a second program, the virtual machine dynamically locates the second program and stores the location of the second program in a table (called a constant pool) so that later references to the second program can be resolved simply by reference to the table. Calls to the second program are then resolved by invoking the procedure at the location indicated in the table.
Referring to FIG. 1, in a computer system 100 that executes Java bytecode programs using a Java virtual machine, dynamic linking of programs is handled by two procedures: a Java class resolver 102 and a Java class loader 104. The Java class loader 104 loads object classes into a work space 106 and, among other things, maintains a table 108 that references all loaded object classes. A bytecode interpreter 110 executes programs 112 that have been loaded into the work space 106 and calls the Java class resolver 102 whenever the interpreter encounters a procedure invoke instruction that has not been previously executed.
The Java class resolver 102 performs the actual dynamic linking of programs by determining if an invoked method is already loaded and calling the class loader 104 if the invoked method is not already loaded. After a reference to the invoked program is resolved, the location of the called procedure is stored in the calling program's constant pool 114, the Java "invoke" instruction in the calling procedure is marked so that future executions of the instruction do not invoke the Java class resolver 102, and the invoke instruction is executed. The invoke instruction, having been resolved, directly invokes the procedure at the location referenced in the calling procedure's constant pool 114.
The Java virtual machine uses the same dynamic linking procedure as just described to resolve references to any object component, not just object class methods. In particular, the Java interpreter detects when an instruction that references an object component is being executed for the first time and calls the Java class resolver to resolve the object component reference. After the reference to the object component has been resolved by the Java class resolver 102, the instruction is executed and is also marked so that future executions of the instruction do not invoke the Java class resolver.
The class loader 104 retrieves object classes either from a locally stored class repository 120, or from remotely located class repositories 122 accessed by a network or Internet communications port 124.
The terms "native program" and "native code" are used in this document to refer to computer programs and instructions that are designed to be directly executed by computers using a specific computer architecture. For instance "68000" code is a type of native code that is designed for execution on systems using Motorola 68000 series microprocessors, and SPARC code is a type of native code that is designed for execution on computer systems using Sun Microsystems' SPARC series microprocessors. Java bytecode programs, by way of contrast, are computer architecture neutral in that they can be executed on any computer system that has a Java virtual machine.
It is difficult to replicate in programs compiled into native code the dynamic linking accomplished by the Java class resolver. More specifically, dynamic linking in a compiled program is relatively easily accomplished. What is difficult is to perform dynamic linking in compiled programs in a computationally efficient manner. An obvious way to implement dynamic linking in compiled programs is to code every procedure call in the program that could possibly be the first instruction to call to a particular program with the following instructions:
If the reference to the Called Program in the constant pool is null PA1 Invoke Called Program at location indicated in constant pool
{ PA2 Call Compiled Program Resolver PA2 }
where the "Compiled Program Resolver" is a program that resolves the reference to the Called Program and updates the constant pool for the calling program to reference the Called Program's location.
The primary problem with the above method for dynamically linking a compiled program at run time is that all procedure calls made using the above "If-Then" set of instructions must execute at least two instructions (i.e., a load instruction and a conditional branch instruction) corresponding to the "If" test prior to executing the procedure call instruction. In fact, in most native code languages the "If-Then" instructions would add three instructions (i.e,. a load, a compare and a conditional branch) prior to the execution of the procedure call instruction. This is very computationally inefficient. A secondary problem with this methodology is that it results in "bloated code" in that the size of a compiled program with this type of dynamically linked procedure calls will be substantially larger than the same compiled program without dynamic linking.